package J7_8;

import java.util.*;

public class test {
    static final double Sigma = 3.3;
    static final int T = 1000;

    //存储有向图
    public static Map<Integer, List<Integer>> map = new HashMap<>();

    //存储 点x 到 点y 的最短路径
    static int[][] arr = new int[10][10];

    static double[][] Lw = new double[10][10];
    static double[] Nw = new double[10];
    static double[][] P = new double[10][10];
    static double[] E = new double[10];
    static double[][] Q = new double[10][10];

    public static void main(String[] args) {
        //初始化带权有向图
        arr[1][2] = arr[2][3] = arr[1][4] = arr[2][5] = arr[3][6] = arr[4][7] = arr[5][8] = arr[6][9] = arr[7][8] = arr[8][9] = 2;
        arr[4][5] = arr[5][6] = 1;
        List<Integer> list = new ArrayList<>();
        list.add(2); list.add(4); map.put(1,list);
        list = new ArrayList<>();
        list.add(3); list.add(5); map.put(2,list);
        list = new ArrayList<>();
        list.add(5); list.add(7); map.put(4,list);
        list = new ArrayList<>();
        list.add(6); list.add(8); map.put(5,list);
        list = new ArrayList<>();
        list.add(6); map.put(3,list);
        list = new ArrayList<>();
        list.add(9); map.put(6,list);
        list = new ArrayList<>();
        list.add(8); map.put(7,list);
        list = new ArrayList<>();
        list.add(9); map.put(8,list);
        list = new ArrayList<>();
        map.put(9,list);

        //调用函数
        calLw();
        calNw();
        calP();
        calQ();
        //输出结果
        for (int x = 1; x <= 9; x++) {
            for (int y = 1; y <= 9; y++) {
                if (Q[x][y] != 0) {
                    //四舍五入
                    int res = (int) Math.round(Q[x][y]);
                    System.out.print(x + " -> " + y + " = " + res + " ");
                }
            }
            System.out.println();
        }
    }
    //计算 点x 到 点9 的最短路径
    public static int getArrMin(int x) {
        if (arr[x][9] != 0) {
            return arr[x][9];
        }
        List<Integer> list = map.get(x);
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < list.size(); i++) {
            int y = list.get(i);
            min = Math.min(min, arr[x][y] + getArrMin(y));
        }
        arr[x][9] = min;
        return min;
    }

    //计算Lw
    public static void calLw() {
        for (int x = 1; x < 9; x++) {
            List<Integer> list = map.get(x);
            double avg = 0;
            double sum = 0;
            int sz = list.size();
            for (int i = 0; i < sz; i++) {
                int y = list.get(i);
                sum += arr[x][y] + getArrMin(y);
            }
            avg = sum / sz;
            for (int i = 0; i < sz; i++) {
                int y = list.get(i);
                Lw[x][y] = Math.exp(-Sigma * (arr[x][y] + getArrMin(y)) / avg);
            }
        }
    }

    public static void calNw() {
        for (int x = 1; x < 9; x++) {
            double sum = 0;
            List<Integer> list = map.get(x);
            int sz = list.size();
            for (int i = 0; i < sz; i++) {
                int y = list.get(i);
                sum += Lw[x][y];
            }
            Nw[x] = sum;
        }
    }

    public static void calP() {
        for (int x = 1; x < 9; x++) {
            List<Integer> list = map.get(x);
            int sz = list.size();
            for (int i = 0; i < sz; i++) {
                int y = list.get(i);
                if (x == 1) {
                    P[x][y] = Lw[x][y] / Nw[x];
                    E[y] += P[x][y];
                } else {
                    P[x][y] = E[x] * Lw[x][y] / Nw[x];
                    E[y] += P[x][y];
                }
            }
        }
    }

    public static void calQ() {
        for (int x = 1; x < 9; x++) {
            List<Integer> list = map.get(x);
            int sz = list.size();
            for (int i = 0; i < sz; i++) {
                int y = list.get(i);
                Q[x][y] = P[x][y] * T;
            }
        }
    }
}
